package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         316,
		Discription: "去除重复元素使得字符串的字典序最小",
		Level:       2,
		Labels: map[string]int{
			"单调栈": 1,
			"哈希表": 1,
		},
	})
}

func RemoveDuplicateLetters(s string) string {
	//尽量维护一个单调栈
	//两种特殊情况
	//栈里已经有字符了，不能进栈（如果把前面的删了，后面进栈，前面被删的位置会变成一个元素更大的，字典序更靠后了，因为单调栈的性质)
	//后面没有该字符了，不能出栈
	leftChCount := make(map[byte]int)
	for i := range s {
		leftChCount[s[i]]++
	}
	incS := make([]byte, 0)

	inStack := make(map[byte]bool, 0)
	for i := range s {
		ch := s[i]
		//栈里已经有相同的ch了
		if inStack[ch] {
			leftChCount[ch]--
			continue
		}

		for len(incS) > 0 {
			topCh := incS[len(incS)-1]
			//当前ch小于栈顶的ch，且栈顶的ch后面还有重复的可以补
			if topCh > ch && leftChCount[topCh] > 0 {
				incS = incS[:len(incS)-1]
				inStack[topCh] = false
			} else {
				break
			}
		}

		incS = append(incS, ch)
		leftChCount[ch]--
		inStack[ch] = true
	}

	return string(incS)
}
